package org.xingole.daily;

/**
 * <a href="https://leetcode.com/problems/count-unguarded-cells-in-the-grid/">Count Unguarded Cells in the Grid</a>
 * 
 * <p>
 * You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays
 * guards and walls where guards[i] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the ith
 * guard and jth wall respectively.
 * 
 * <p>
 * A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position
 * unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.
 */
public class CountUnguardedCellsInTheGrid {

    private static final int UNGUARDED = 0; // An unguarded cell
    private static final int GUARDED = 1;   // A cell that is guarded
    private static final int GUARD = 2;     // A cell with a guard
    private static final int WALL = 3;      // A wall cell

    /**
     * Return the number of unoccupied cells that are not guarded.
     */
    public int countUnguarded2(int m, int n, int[][] guards, int[][] walls) {
        /*
         * Apporach 2: Recursive Way
         * 
         * We begin by marking the positions of the guards and walls in the grid, just like in the first approach.
         * Then, for each guard, we trigger recursion in all four directions. Each recursive call will explore one
         * direction as far as possible, marking all the reachable cells as "guarded". The exploration stops when it
         * encounters a wall or another guard, and we repeat this process wiht other guards.
         * 
         */
        int[][] grid = new int[m][n];

        // Mark guard's positions
        for (int[] guard : guards) {
            grid[guard[0]][guard[1]] = GUARD;
        }

        // Mark wall's positions
        for (int[] wall : walls) {
            grid[wall[0]][wall[1]] = WALL;
        }

        // Mark cells as guarded by traversing from each guard
        for (int[] guard : guards) {
            markguarded(guard[0], guard[1], grid);
        }

        // Count unguarded cells
        int count = 0;
        for (int[] row : grid) {
            for (int cell : row) {
                if (cell == UNGUARDED) {
                    count++;
                }
            }
        }

        return count;
    }
    
    /**
     * Mark cells as guarded.
     */
    private void markguarded(int row, int col, int[][] grid) {
        // Traverse upwards
        for (int r = row - 1; r >= 0; r--) {
            if (grid[r][col] == WALL || grid[r][col] == GUARD) break;
            grid[r][col] = GUARDED;
        }

        // Traverse downwards
        for (int r = row + 1; r < grid.length; r++) {
            if (grid[r][col] == WALL || grid[r][col] == GUARD) break;
            grid[r][col] = GUARDED;
        }

        // Traverse leftwards
        for (int c = col - 1; c >= 0; c--) {
            if (grid[row][c] == WALL || grid[row][c] == GUARD) break;
            grid[row][c] = GUARDED;
        }

        // Traverse rightwards
        for (int c = col + 1; c < grid[0].length; c++) {
            if (grid[row][c] == WALL || grid[row][c] == GUARD) break;
            grid[row][c] = GUARDED;
        }
    }
}
